package com.jxm.graph;

/**
 * @Author: jxm
 * @Description: 深度优先搜索
 * @Date: 2022/8/1 15:46
 * @Version: 1.0
 */
public class DepthFirstSearch {

    // 存储顶点  索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;

    /**
     * 构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点
     * 的所有相通顶点
     * @param G
     * @param s
     */
    public DepthFirstSearch(Graph G,int s){
        //初始化marked数组
        this.marked = new boolean[G.V()];
        //初始化跟顶点s相通的顶点数量
        this.count = 0;

        dfs(G,s);
    }

    /**
     * 使用深度优先搜索找出G图中v顶点的所有相通顶点
     * @param G
     * @param v
     */
    private void dfs(Graph G, int v){
        //把v顶点标识为已搜索
        marked[v] = true;

        for (Integer w : G.adj(v)) {
            //判断当前w顶点有没有被搜索过，如果没有被搜索过，则递归调用dfs方法进行深度搜索
            if(!marked(w)){
                dfs(G,w);
            }
        }
        //相通顶点个数+1
        count++;

    }

    /**
     * 判断w顶点与s顶点是否相通
     * @param w
     * @return
     */
    public boolean marked(int w){
        return marked[w];
    }

    /**
     * 获取与顶点s相通的所有顶点的总数
     * @return
     */
    public int count(){
        return count;
    }
}
